1. Fie1d of the Invention
The present invention relates to the field of encryption devices and methods, and more particularly, to block substitution encryption methods and devices.
2. Prior Art
In many cases, it is desired to communicate information in digital form from one location to another in a manner which is clear and unambiguous to the receiver, but which is incomprehensible to an interloper therebetween. Accordingly, in many instances, it is common to encrypt the information to be communicated by some predetermined encryption process, to transmit the encrypted form of the information and to then decrypt the information at the receiving location. Depending upon the degree of security desired, a relatively simple and easily broken encryption may be used, as any level of encryption will make the transmission meaningless to the casual interloper. In other situations, the degree of security desired may dictate the use of an encryption technique which is more difficult to decipher by cryptanalysis, or of course hopefully in the highest level of security, make the same substantially impossible to decipher. Applications for such encryption techniques include commercial applications such as sensitive communications between manufacturing plants, bank branches, etc., and military applications including but not limited to IFF (identification friend or foe). While in some cases the primary objective of the encryption is to prevent an interloper from deciphering the information being communicated, in other cases a primary object, such as in IFF, is to prevent the interloper from himself originating false information with the same encryption scheme so as to mislead the intended receiver. Both objectives are frequently present in many applications.
Block substitution is a method used to encrypt a clear text message which is in the form of a sequence of binary numbers. In accordance with the method, the sequence is broken into blocks of some predetermined block length n, with the block substitution device substituting a unique new block of binary numbers for each of those in the clear text. Substitute blocks constitute the encrypted message or cipher text, each substitute block representing a nonambiguous one-to-one transformation of a clear text block. In the prior art, such substitution generally takes place by means of look-up tables, switching arrangements, or feedback shift registers. However, without changing codes or substitution schemes frequently, the encryption may be broken by cryptanalysis, though, changing look-up tables is cumbersome, only a limited number of possible switching arrangements is practical, and repeated cycling of a shift register is time consuming. An additional problem arises in finding substitutions which do not have any pattern or bias in them. At the present time, candidate substitutions are examined by computer simulation for possible systematic patterns and in some cases, additional circuitry is used to compensate therefor.
Various types of encryption equipment and methods are well-known in the prior art. See for instance U.S. Pate. No. 3,796,830, 3,798,359, 4,078,152, 4,195,200, 4,255,811, 4,316,055 and 4,520,232. In general these systems they relate to block substitution are key dependent ciphering and deciphering systems and are not based upon block substitution by modulo 2 addition of one additive permuted set of numbers to another, as in the present invention.
In the parent application, methods and apparatus for modulo 2 addition based encryption by block substitution techniques were disclosed which allow use of the substitution scheme with relatively simple hardware. The block substitution, a one to one mapping of n bit binary numbers onto themselves, is based on the fact that certain permutations of the n bit binary numbers define a block substitution by modulo 2 addition of one permuted set of numbers to another, and that a subset of these define equations having an additive relationship when viewed as vectors, whereby the remainder of the set may be generated from a limited subset of the equations. This allows the simple changing of the transformation on a frequent basis. Various properties of the transformations and methods of using the same were disclosed. The fact that the remainder of the set equations may be generated from a limited subset of the equations, however, may make cryptanalysis less difficult than desired in some applications. Accordingly the present invention comprises a method and apparatus for nonlinearizing the equations, also in an orderly and readily variable manner, so that the remainder of the set equations may no longer be generated from a limited subset of the equations.